МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра “Телекомунікації”
ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА Методичні вказівки до лабораторної роботи № 3 з курсу «Методи кодування інформації» для студентів базового напрямку «Телекомунікації» Львів 2001 “Дослідження кодів Хемінга”. Методичні вказівки до лабораторної роботи № 3 з курсу “Методи кодування інформації” для студентів базового напрямку 0924 - “Телекомунікації”. - Львів 2001. – 6 с. Автори: доцент Коваль Б.В. ст. викладач Чайковський І.Б. Рецензенти: професор, д.т.н. Оганесян А.Г. доцент, к.т.н. Волочій Б.Ю. У лабораторній роботі досліджується процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності. Методичні вказівки затверджено на засіданні кафедри “Телекомунікації” Національного університету “Львівська політехніка” 04.04.2001 р., протокол № 8. Мета роботи Дослідити процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності. Теоретична частина. Одним з найбільш поширених систематичних кодів є код Хемінга. Відомо декілька різновидностей цих кодів, що характеризуються різними коректуючими здатностями. До них кодів звичайно відносяться коди з мінімальною кодовою відстанню dmin=3, які виправляють всі одиночні помилки, і коди з відстанню dmin=4, які виправляють всі одиночні і виявляють всі подвійні помилки, або ж виявляють всі потрійні помилки. Код Хемінга є одним з небагатьох досконалих кодів, для яких виконується ідеальне співвідношення між довжиною коду п та кількістю перевірочних r або інформаційних к розрядів, що випливає з виразу (1) для границі Хемінга: п2 r-1 (1) Досконалий код Хемінга має кодову відстань dmin=3 і відповідає випадку, коли досягається крайнє значення границі Хемінга: n=2 r-1. Отже, його параметри (n, k) = (2 r-1, 2 r-1-r),’ де r=2, 3,... - кількість перевірочних розрядів. В табл.1 наведені параметри деяких кодів Хеммінга. Коди Хемінга відносяться до швидких кодів. Характерною особливістю матриці перевірки Н коду з dmin=3 є те, що її стовбці представляють собою будь-які ненульові комбінації довжиною r. Отже ми, наприклад, можемо отримати матрицю Н для коду (15, 11), з r=4 i n=15, записавши у двійковому вигляді всі числа від 1 до (2 r-1)=15 у вигляді стовбчиків матриці: Н15,11= EMBED Equation.2 
 (2) Перестановкою стовбців, що містять одну одиницю, дану матрицю можна звести до канонічної форми: Н15,11= EMBED Equation.2 
 (3) Кодування Знаючи матрицю Н, легко побудувати матрицю G і всі її робочі кодові комбінації. Декодування Отримавши кодову комбінацію (КК), ми обчислюємо синдром і дивимось, з яким стовбцем матриці він співпадає: - якщо синдром рівний нулеві, прийнята КК вважається правильною і з неї видаляємо перевірочні розряди; - якщо синдром не нульовий, тоді знаходимо номер стовбчика матриці Н, що рівний синдромові, і виправляємо помилку у розряді прийнятої КК, що має цей же номер, або робимо висновок, що прийнята КК - помилкова. Хемінг запропонував використовувати матрицю Н не в канонічному вигляді (3), а у вигляді (2) -номер стовбчика у двійковому вигляді співпадає з елементами у цьому ж стовбчику. Тоді перевірочні розряди КК повинні знаходитись не в кінці КК, а на номерах позицій, що відповідають степені 2: 20, 21, 22,..., 2 r-1. У цьому випадку синдром, отриманий з прийнятої КК, буде двійковим номером розряда КК, у якому виникла помилка, що значно полегшує процес декодування. Наприклад, для матриці (2) перевірочними будуть 1, 2, 4 та 8 розряди, а інформаційними - 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15. Повідомлення 11010101011 після кодування матиме вигляд 011110100101011. Якщо помилка виникла в 7-ому розряді, тоді прийнята КК бу...